package com.zhugang.week13.tree;

/**
 * @program algorithms
 * @description: EQueen
 * @author: chanzhugang
 * @create: 2022/10/08 17:50
 */
public class EQueen {

    // queens[0] = 3 表示第一列皇后放在第4行
    int[] queens = new int[8];

    /**
     * 每次找一列，把皇后放在这一列的哪一行
     * 递归
     *
     * @param col
     * @return
     */
    public boolean solve(int col) {
        if (col == 8) {
            return true;
        }
        // i 表示 row
        for (int i = 0; i < 8; i++) {
            // 尝试col列 皇后放在第i行
            queens[col] = i;

            boolean flag = true;

            // 放在这一行是否满足，和之前的列比较，j是之前处理好的列
            for (int j = 0; j < col; j++) {
                int rowDiff = Math.abs(queens[j] - i);
                int colDiff = col - j;
                if (rowDiff == colDiff || queens[j] == i) {
                    // 对角线、 水平线 相等，不满足
                    flag = false;
                    // 剪枝
                    break;
                }
            }
            // 满足递归下一列
            if (flag && solve(col + 1)) {
                return true;
            }
        }
        return false;
    }

    void print() {
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                if (queens[i] == j) {
                    System.out.print("Q");
                } else {

                    System.out.print(".");
                }
            }
            System.out.print("\n");
        }
    }

    public static void main(String[] args) {
        var equeen = new EQueen();
        equeen.solve(0);
        equeen.print();
    }
}